package code201_300.code1_10;

/**
 * 编写一个算法来判断一个数 n 是不是快乐数。
 *
 * 「快乐数」定义为：
 *
 * 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
 * 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
 * 如果 可以变为  1，那么这个数就是快乐数。
 * 如果 n 是快乐数就返回 true ；不是，则返回 false 。
 *
 * 输入：n = 19
 * 输出：true
 * 解释：
 * 12 + 92 = 82
 * 82 + 22 = 68
 * 62 + 82 = 100
 * 12 + 02 + 02 = 1
 *
 * 输入：n = 2
 * 输出：false
 */
public class _202isHappy {

    /**
     * 先暂定这个无限循环超出int即停止,实验证明是不可行的，因为无限循环可能不超出int最大值的一半再一直循环，观看评论总结
     *
     * 只有两种方法：1.直接遍历所有数，找到一直循环的数记录下来。真正输入的时候只要循环到了这个位置，直接false
     * 2：所有无限死循环肯定是因为又重新回到了原来的自己，所以类似于快慢指针判断链表是否存在环的问题。
     * 快指针循环的时候和慢指针相等了，那直接就return false
     *
     *
     * @param n
     * @return
     */
    /*public boolean isHappy(int n) {
        if(n==1) return true;
        while (n!=1){
            if(n>Integer.MAX_VALUE/2)return false;
            int temp = 0;
            while (n>0){
                temp += (n%10)*(n%10);
                n = n/10;
            }
            n = temp;
        }
        return true;
    }*/

    public static int pow(int n){
        int temp = 0;
        while (n>0){
            temp += (n%10)*(n%10);
            n = n/10;
        }
        return temp;
    }

    /**
     * 快慢指针实现，有时候不要想着走捷径，该单独提出个方法就提。代价没有想象中的那么大
     *
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 35.4 MB     * , 在所有 Java 提交中击败了     * 63.62%     * 的用户
     *
     * @param n
     * @return
     */
    public static boolean isHappy(int n) {
        if(n==1)return true;
        // 定义快慢指针
        int lower = n;
        int quick = 0;
        while (n>0){
            quick += (n%10)*(n%10);
            n = n/10;
        }
        while (lower!=1&&quick!=1){
            // 如果一个追上了另一个 则证明有无限循环存在 return false
            if(lower == quick)return false;
            // 快慢指针实现
            lower = pow(lower);
            quick = pow(quick);
            quick = pow(quick);
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isHappy(19));
    }

}
